package Hot_100;

/*
    14. 最长公共前缀
    编写一个函数来查找字符串数组中的最长公共前缀。
    如果不存在公共前缀，返回空字符串 ""。
    https://leetcode.cn/problems/longest-common-prefix/
* */
public class T14_longestCommonPrefix {
    public static void main(String[] args) {
        String[] strArr = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix_1(strArr));
    }


//    2.
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
            return "";

        String ans = strs[0];             //初始化结果串为字符串数组的第一个元素
        for(int i =1;i<strs.length;i++) { //i是用来遍历字符串数组的指针
            int j=0;                      //j是遍历每个字符串的指针
            for(;j<ans.length() && j < strs[i].length();j++) {  //比较第0个字符串和后序的n-1个字符串
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);  //截取两个字符串的公共部分
            if(ans.equals(""))          //ans为空串，说明不存在公共前缀，直接返回
                return ans;
        }

        return ans;
    }



//    1. 暴力解法
    public static String longestCommonPrefix_1(String[] strs) {

        int minLen=Integer.MAX_VALUE;
//        取字符串数组中的最小长度
        for (int j = 0; j < strs.length; j++) {
            int len=strs[j].length();
            if (len < minLen) {
                minLen=len;
            }
        }
        String comStr="";

        for (int i = 0; i < minLen; i++) {
            char ch=strs[0].charAt(i);                  //取第一个字符串的第i个字符
            for (int j = 1; j < strs.length; j++) {
                if (ch != strs[j].charAt(i)) {
                    return comStr;
                }
            }
            comStr+=ch;
        }
        return comStr;
    }
}